1) Field of the Invention
The present invention relates to a technology for predicting a branch target address of a branch instruction and making a judgment whether the predicted branch target address agrees with an actual branch target address at a high speed.
2) Description of the Related Art
In an information processing apparatus that adopts a high degree instruction processing method following the pipeline processing method, performance is improved by starting the processing for the subsequent instruction speculatively, without waiting for the execution of one instruction.
When a branch instruction is to be executed, however, an instruction address to be executed next cannot be known unless one instruction has been executed, and hence the processing for the subsequent instruction cannot be started. Therefore, attention has been given to a technique in which by predicting an instruction address to be executed next, the processing for the subsequent instruction can be started before executing a branch instruction.
For example, Japanese Patent Application Laid-Open No. H6-89173 discloses a technique of predicting an instruction address to be executed next using a branch history. In this conventional art, a branch instruction address executed in the past and a branch target address thereof are registered in the branch history, corresponding to each other. When a branch instruction registered in the branch history is to be executed newly, an instruction address to be executed next is predicted using the branch target address corresponding to the branch instruction.
Japanese Patent Application Laid-Open No. 2000-172507 discloses a technique of increasing a prediction accuracy of a branch target address of a subroutine return instruction. In the subroutine return instruction, the branch target address changes, and therefore the branch target address in the past registered in the branch history is often different from an actual branch target address, and hence the prediction is quite possible to fail. Therefore, in this conventional art, when a return address in a return address stack that stores subroutine return addresses, agrees with a branch target address in the branch history, the address is designated as a predicted address of the subsequent instruction, thereby improving the prediction accuracy.
However, when the processing for the subsequent instruction is to be performed speculatively using such a branch prediction technique, it is necessary to cancel the executed processing for the subsequent instruction if the prediction is failed. Therefore, at a point of time when the actual branch target address is calculated, it is necessary to judge whether the actual branch target address agrees with the predicted branch target address by comparing these addresses. It is also necessary that this judgment is carried out on the same pipeline stage as that for the calculation of the actual branch target address, so that the processing performance is not deteriorated.
However, as the clock cycle has become fast recently, it becomes difficult to carry out the calculation of the actual branch target address, and comparison between the calculated actual branch target address and the predicted branch target address in one cycle of the pipeline. As a result, the processing performance deteriorates. Therefore, it becomes necessary to carry out the calculation of the actual branch target address, and comparison between the calculated actual branch target address and the predicted branch target address in different cycle of the pipeline.